class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        int[][] dp= new int[n][n];
        for(int i = n - 1; i >= 0; i--){
            for(int j = i; j < n; j++){
                char start = s.charAt(i);
                char end = s.charAt(j);
                if(start == end){
                    if(i == j) dp[i][j] = 1;
                    else if(i + 1 == j) dp[i][j] = 2;
                    else{
                        if(dp[i + 1][j - 1] > 0) dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }
            }
        }
        for(int i = 1; i < n - 1; i++){
            for(int j = i; j < n - 1; j++){
                if(dp[0][i - 1] > 0 && dp[i][j] > 0 && dp[j + 1][n - 1] > 0){
                    return true;
                }
            }
        }
        return false;
    }
}